// https://www.lintcode.cn/problem/shortest-path-in-undirected-graph/description

/**
 * Definition for Undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: a list of Undirected graph node
     * @param A: nodeA
     * @param B: nodeB
     * @return:  the length of the shortest path
     */
    // 法一：bfs
    // int shortestPath(vector<UndirectedGraphNode*> graph, UndirectedGraphNode* A, UndirectedGraphNode* B) {
        // queue<UndirectedGraphNode*> record;
        // record.push(A);
        // map<int, int> dis;
        // dis[A->label] = 0;
        // while (!record.empty())
        // {
        //     UndirectedGraphNode* tmp = record.front();
        //     record.pop();
        //     if (tmp == B) return dis[tmp->label];
        //     for (auto n: tmp->neighbors)
        //     {
        //         if (dis.find(n->label) == dis.end())
        //         {
        //             dis[n->label] = dis[tmp->label] + 1;
        //             record.push(n);
        //         }
        //     }
        // }
        // return -1;
    // }
    
    // 法二：双向bfs
    int shortestPath(vector<UndirectedGraphNode*> graph, UndirectedGraphNode* A, UndirectedGraphNode* B) 
    {
        queue<UndirectedGraphNode*> record1;
        record1.push(A);
        set<UndirectedGraphNode*> set1;
        set1.insert(A);
        queue<UndirectedGraphNode*> record2;
        record2.push(B);
        set<UndirectedGraphNode*> set2;
        set2.insert(B);
        int len = 0;
        while (!record1.empty() || !record2.empty())
        {
            len++;
            int size = record1.size();
            UndirectedGraphNode* tmp;
            for (int i = 0; i < size; ++i)
            {
                tmp = record1.front();
                record1.pop();
                for (auto n: tmp->neighbors)
                {
                    if (set2.find(n) != set2.end()) return len;
                    if (set1.find(n) == set1.end())
                    {
                        set1.insert(n);
                        record1.push(n);
                    }
                }
            }            
            len++;
            size = record2.size();
            for (int i = 0; i < size; ++i)
            {
                tmp = record2.front();
                record2.pop();
                for (auto n: tmp->neighbors)
                {
                    if (set1.find(n) != set1.end()) return len;
                    if (set2.find(n) == set2.end())
                    {
                        set2.insert(n);
                        record2.push(n);
                    }
                }
            } 
            cout << endl;
        }
        return -1;
    }
};